//-----------------------------------------------------------------------------
//
// @file	Octree.h
// @brief	Octree data structure with iterator to traverse its leaves
// @author	Vinod Melapudi
// @date	13Aug2011
//
//-----------------------------------------------------------------------------

#ifndef _OCTREE_H
#define _OCTREE_H


#include "Utils.h"
#include "Vector3T.h"

class MemPool;


template<class T>
class Octree
{
public:
	// Size - dimension of octree in one axis
	// This will create octree with size*size*size leaves
	Octree( uint size );
	~Octree();


	// Accessors: Set/Get data at given location
	void	Set( const uLocation& l, T data );
	T*		Get( const uLocation& l ) const;
	T*		operator()( const uLocation& l ) const;



	// Functions to setup & used by iterators
	class iterator;
	iterator	Begin() const		{	return m_begin;	}
	iterator	End() const			{	return m_end;	}
	iterator	Iter( const uLocation& l ) const;


	// Iterator implementation (points to leaf with data)
	// Has path from root to leaf
	// Can iterate to next leaf with data
	// Can iterate to next leaf with data in given axis	class iterator
	class iterator
	{
	public:
		iterator() : m_octree(NULL), m_data_ptr(NULL), m_location(0,0,0)	{}

		// Operators
		iterator&	operator++();								// Get next leaf
		iterator&	operator--();								// Get next leaf
		bool		operator<( const iterator& rhs ) const;		// Compare locations of 2 leaves
		bool		operator==( const iterator& rhs ) const;
		T*			operator*() const							{	return m_data_ptr;	}

		// Accessors
		T*				GetData() const				{	return m_data_ptr;	}
		uLocation		GetLocation() const			{	return m_location;	}

		// Make parent friend, so it can access private members to set data and location
		friend	Octree;

	private:
		// Functions used by parent class
		inline void	Set( const Octree<T>* octree, T* data_ptr, const uLocation& loc )
		{
			m_octree = octree;
			m_data_ptr = data_ptr;
			m_location = loc;
		}
		inline void	Set( const Octree<T>* octree, T* data_ptr )
		{
			m_octree = octree;
			m_data_ptr = data_ptr;
		}
		inline uLocation&	Location()	{ return m_location; }
		inline void			PushLocation( short idx );
		inline void			PopLocation();

	private:
		const Octree<T>* 		m_octree;		// Ptr to parent
		T*						m_data_ptr;		// Ptr to data
		uLocation				m_location;		// Location of data
	};




private:

	// Node structure
	struct Node
	{
		bool leaf;
	};

	// Branch node
	struct Branch: public Node
	{
		Branch()
		{
			leaf = false;

			Node** first = &m_children[0][0][0];
			for( uint i=0; i < 8; i++ )
				*(first+i) = NULL;
		}

		// Accessor to get child
		inline Node*	Child( short x, short y, short z )		{	return m_children[x][y][z];	}
		inline Node*	Child( short idx )						{	return *(&m_children[0][0][0]+idx);	}

		Node*	m_children[2][2][2];
	};

	// Leaf node
	struct Leaf: public Node
	{
		Leaf()
		{
			leaf = true;
		}
		T	m_data;
	};

	// Convenience typedef
	typedef		std::vector<Branch*>	PathBranches;


private:
	Octree()	{}
		
	// Get list of branches the current iterator points to
	void	GetPathBranches( iterator& iter, PathBranches& path_branches ) const;

	// Given a iterator, update it with the path to next leaf in the given direction
	void	UpdateIterator( iterator& iter, bool positive_dir ) const;

	// Recursively iterate down a given branch node, to the 1st or last leaf node & also get the path
	bool	FindLeafPathAt( Node* node, iterator& iter, bool positive_dir ) const;



private:
	Node*		m_root;			// Root

	uint		m_size;			// Size of octree

	iterator	m_begin;		// Iterator cache
	iterator	m_end;

	MemPool*	m_branch_pool;	// Mempools
	MemPool*	m_leaf_pool;
};


// Octree testing
bool OctreeTest();

#include "Octree.cpp"

#endif